package com.xy6.algo.divide;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 分治法求解最近点对问题
 * 
 * <pre>
 * 问题描述：给定平面上n个点(n>2)，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。
 * 严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。
 * 时间复杂度：nlogn
 * 该算法依赖排序算法
 * 递推式：T(n)=2T(n/2)+M(n)，M(n)是合并较小子问题所用的时间
 * 可以得出T(n)属于O(nlogn)
 * 
 * https://www.cnblogs.com/zyxStar/p/4591897.html
 * </pre>
 * 
 * @author zhang
 * @since 2018-02-22
 */
public class CloestPoints {

	private static double inf = Double.MAX_VALUE;
	private static int maxn = 200005;

	private Point[] point = new Point[maxn];
	private Integer[] mpt = new Integer[maxn];
	// 点的个数
	private int n;
	// 距离最近的两个点
	public int p1, p2;
	// 两个点的距离
	private double min = 0;
	public static boolean showLog = true;

	/**
	 * 求解最近点对，对外开放的接口
	 * 
	 * @param x
	 * @param y
	 * @return
	 */
	public double closest(double[] x, double[] y) {
		n = x.length;
		for (int i = 0; i < n; i++) {
			point[i] = new Point(x[i], y[i]);
		}
		printPoint();
		sort(point, n - 1, new MyComparator2());
		printPoint();
		double dis = closest(0, n - 1);
		println(String.format("%nmin distance: %f", dis));
		println(String.format("point[%d]: %f, %f", p1, point[p1].x, point[p1].y));
		println(String.format("point[%d]: %f, %f", p2, point[p2].x, point[p2].y));

		return dis;
	}

	/**
	 * 分治求解最近点对
	 * 
	 * @param left
	 * @param right
	 * @return
	 */
	private double closest(int left, int right) {
		println(String.format("left:%d, right:%d", left, right));
		double d = inf;
		// 递归终止
		if (left == right) {
			println(String.format("left:%d, right:%d, return1:%f", left, right, d));
			return d;
		}
		if (left + 1 == right) {
			double dis = dis(left, right);
			println(String.format("left:%d, right:%d, return2:%f", left, right, dis));
			return dis;
		}
		
		// 1 将区间分为两部分p1[left,mid] p2[mid+1,right]，分别求最近距离d1 d2
		int mid = (left + right) >> 1;
		println(String.format("left:%d, mid:%d, right:%d", left, mid, right));
		double d1 = closest(left, mid);
		println(String.format("left:%d, mid:%d, d1:%f", left, mid, d1));
		double d2 = closest(mid + 1, right);
		println(String.format("mid+1:%d, right:%d, d2:%f", mid + 1, right, d2));
		// 取两个距离的最小值
		if (d1 < d2) {
			d = d1;
			// 记录最近距离的两个点
			if (d < min || min == 0) {
				min = d;
				p1 = left;
				p2 = mid;
			}
		} else {
			d = d2;
			if (d < min || min == 0) {
				min = d;
				p1 = mid + 1;
				p2 = right;
			}
		}
		println(String.format("p1:%d, p2:%d, d:%f", p1, p2, d));
		
		int i, j, k = 0;
		// 2 计算横跨p1 p2区间的最近的两个点的距离。计算时加条件：距离<已知的最小值d
		// 分离出宽度为d的区间，按x坐标进行过滤。
		// 先考虑x坐标，如果存在<d的两个点，这两个点x之差一定<d。
		// 勾股定理，斜边<d，两个直角边一定<d。此处考虑性能，放宽了限制条件
		for (i = left; i <= right; i++) {
			if (Math.abs(point[mid].x - point[i].x) <= d) {
				mpt[k++] = i;
			}
		}
		// 将点按y值升序排列
		sort(mpt, k - 1, new MyComparator1());
		for (int l = 0; l < k; l++) {
			println(String.format("mpt[%d], x:%f, y:%f", mpt[l], point[mpt[l]].x, point[mpt[l]].y));
		}

		// 线性扫描。遍历过滤后的点，加条件：两个点的y之差一定<d
		for (i = 0; i < k; i++) {
			for (j = i + 1; j < k; j++) {
				// 如果当前点不符合，后续点一定不符合。因为点已按y值升序排列
				if(point[mpt[j]].y - point[mpt[i]].y >= d){
					break;
				}
				// 如果两点x之差>=d，两点距离一定>=d，不符合
				if(Math.abs(point[mpt[j]].x - point[mpt[i]].x) >= d){
					continue;
				}
				double d3 = dis(mpt[i], mpt[j]);
				if (d > d3) {
					d = d3;
					// 记录最近距离的两个点
					if (d < min || min == 0) {
						min = d;
						p1 = mpt[i];
						p2 = mpt[j];
						println(String.format("p1:%d, p2:%d, d3:%f", mpt[i], mpt[j], d3));
						println(String.format("p1.x:%f, p1.y:%f", point[mpt[i]].x, point[mpt[i]].y));
						println(String.format("p2.x:%f, p2.y:%f", point[mpt[j]].x, point[mpt[j]].y));
					}
				}
			}
		}

		println(String.format("left:%d, right:%d, return3:%f, p1:%d, p2:%d", left, right, d, p1, p2));
		return d;
	}

	/**
	 * 计算两点的距离
	 * 
	 * @param i
	 * @param j
	 * @return
	 */
	private double dis(int i, int j) {
		return Math.sqrt((point[i].x - point[j].x) * (point[i].x - point[j].x) + (point[i].y - point[j].y)
				* (point[i].y - point[j].y));
	}

	/**
	 * 对数组[0,endIndex]范围的元素进行排序。
	 * 使用jdk提供的排序算法实现，归并排序，未自己实现排序算法。
	 * 
	 * @param arr
	 * @param endIndex
	 * @param c 比较器
	 */
	@SuppressWarnings("unchecked")
	private <T> void sort(T[] arr, int endIndex, Comparator<? super T> c) {
		T[] subarr = Arrays.copyOfRange(arr, 0, endIndex + 1);
		Arrays.sort(subarr, (Comparator<T>) c);
		// 更新原数组
		for (int i = 0; i < endIndex + 1; i++) {
			arr[i] = subarr[i];
		}
		subarr = null;
	}

	public static void main(String[] args) {
		CloestPoints p = new CloestPoints();
		p.testThreePoints();
	}

	private void testThreePoints() {
		double[] arrx = new double[] { 0, 1, 2 };
		double[] arry = new double[] { 2, 0, 2 };
		closest(arrx, arry);
	}

	/**
	 * 打印所有的点
	 */
	private void printPoint() {
		for (int i = 0; i < n; i++) {
			println(String.format("%f, %f", point[i].x, point[i].y));
		}
		println("");
	}
	
	/**
	 * 自定义输出，方便关闭打印日志，测试性能
	 */
	private void println(String str){
		if(showLog){
			System.out.println(str);
		}
	}

	private class Point {
		private double x;
		private double y;

		public Point(double x, double y) {
			this.x = x;
			this.y = y;
		}
	}

	/**
	 * 比较两个点y值大小。输入为y值
	 */
	private class MyComparator1 implements Comparator<Integer> {
		@Override
		public int compare(Integer a, Integer b) {
			if (point[a].y != point[b].y) {
				return point[a].y < point[b].y ? -1 : 1;
			}
			return 0;
		}
	}

	/**
	 * 比较两个点的坐标，先比较x大小，再比较y大小
	 */
	private class MyComparator2 implements Comparator<Point> {
		@Override
		public int compare(Point a, Point b) {
			if (a.x != b.x) {
				return a.x < b.x ? -1 : 1;
			}
			return a.y == b.y ? 0 : (a.y < b.y ? -1 : 1);
		}
	}

}
